package offer;

import java.util.*;

/**
 * Creared with IntelliJ IDEA.
 * Description:输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，找到一个具有最大和的连续子数组。
 * 1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 * 2.如果存在多个最大和的连续子数组，那么返回其中长度最长的，该题数据保证这个最长的只存在一个
 * 3.该题定义的子数组的最小长度为1，不存在为空的子数组，即不存在[]是某个数组的子数组
 * 4.返回的数组不计入空间复杂度计算
 * User:yxd
 * Date:2022-07-10
 * Time:0:42
 */
public class JZ85 {
    public static int[] FindGreatestSumOfSubArray (int[] array) {
        int x = array[0];
        int y = 0;
        int maxsum = x;
        //滑动区间
        int left = 0, right = 0;
        //记录最长的区间
        int resl = 0, resr = 0;
        for(int i = 1; i < array.length; i++){
            right++;
            //状态转移：连续子数组和最大值
            y = Math.max(x + array[i], array[i]);
            //区间新起点
            if(x + array[i] < array[i])
                left = right;
            //更新最大值
            if(y > maxsum || y == maxsum && (right - left + 1) > (resr - resl + 1)){
                maxsum = y;
                resl = left;
                resr = right;
            }
            //更新x的状态
            x = y;
        }
        //取数组
        int[] res = new int[resr - resl + 1];
        for(int i = resl; i <= resr; i++)
            res[i - resl] = array[i];
        return res;
    }


    public static int[] FindGreatestSumOfSubArray1 (int[] array) {
        // write code here
        //状态定义：到F(n)的最大和连续长子序列,记录和
        //状态转移方程：F(n) = 如果前一个F(n)>=0 为 F（n- 1） + array[n]
        //else F（n）= array[n]
        //赋初值 F(0) = 0; F(1) = array[1];
        int[] dp = new int[array.length];//第二列表示当前的最长序列数
        dp[0] = array[0];
        //记录最大序列和
        int sum = Integer.MIN_VALUE;
        int sum1 = Integer.MIN_VALUE;
        //记录其下标
        int index = 0;
        int index1 = 0;
        //记录子串长度
        int num = 1;
        //记录最长的子串长度
        int count = 0;
        for(int i = 1;i < array.length;i ++){
            if(dp[i - 1] >= 0){
                dp[i] = dp[i - 1] + array[i];
                num ++;
            }else{
                dp[i] = array[i];
                num = 1;
            }

            if(dp[i] >= sum){

                sum = dp[i];
                index = i;
                //如果有相等的，就取最长的一个子串
                if(dp[i] == sum){
                    //这里需要记录下来最长的，并且需要记录下来结束位置和大小
                    if(num > count){
                        count = num;
                        index1 = i;
                        sum1 = sum;
                    }
                }
            }
            if(dp[i] < 0 && dp[i - 1] > 0){
                //特殊情况走到最后一个，有可能值判断了前一个的情况，而没有看最后一个情况，导致数量多了一个就应该减去
                num --;
            }
        }
        int[] nums;
        //这里需要判断一下sum是不是和sum1相等，如果相等，就需要用index1和count,表示使用最长的一个序列
        if(sum == sum1){
            nums = new int[count];
            int i = count - 1;
            while(count-- != 0){
                nums[i] = array[index1];
                i --;
                index1 --;
            }
        }else{
            nums = new int[num];
            int i = num - 1;
            while(num-- != 0){
                nums[i] = array[index];
                i --;
                index --;
            }
        }

        return nums;
    }

    public static void main(String[] args) {
        int[] a = {1,2,-3,4,-1,1,-3,2};
        int[] x = FindGreatestSumOfSubArray(a);
        System.out.println(Arrays.toString(x));
    }
}
